package array;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个正整数数组 queries ，其取值范围在 1 到 m 之间。 请你根据以下规则按顺序处理所有 queries[i]（从 i=0 到 i=queries.length-1）：
 * 首先，你有一个排列 P=[1,2,3,...,m]。
 * 对于当前的 i ，找到 queries[i] 在排列 P 中的位置（从 0 开始索引），然后将它移到排列 P 的开头（即下标为 0 处）。注意， queries[i] 的查询结果是 queries[i] 在 P 中移动前的位置。
 * 返回一个数组，包含从给定  queries 中查询到的结果。
 * <p>
 * 示例 1：
 * 输入：queries = [3,1,2,1], m = 5
 * 输出：[2,1,2,1]
 * 解释：处理 queries 的过程如下：
 * 对于 i=0: queries[i]=3, P=[1,2,3,4,5], 3 在 P 中的位置是 2，然后我们把 3 移动到 P 的开头，得到 P=[3,1,2,4,5] 。
 * 对于 i=1: queries[i]=1, P=[3,1,2,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,3,2,4,5] 。
 * 对于 i=2: queries[i]=2, P=[1,3,2,4,5], 2 在 P 中的位置是 2，然后我们把 2 移动到 P 的开头，得到 P=[2,1,3,4,5] 。
 * 对于 i=3: queries[i]=1, P=[2,1,3,4,5], 1 在 P 中的位置是 1，然后我们把 1 移动到 P 的开头，得到 P=[1,2,3,4,5] 。
 * 因此，包含结果的数组为 [2,1,2,1] 。
 * <p>
 * 示例 2：
 * 输入：queries = [4,1,2,2], m = 4
 * 输出：[3,1,2,0]
 * <p>
 * 示例 3：
 * 输入：queries = [7,5,5,8,3], m = 8
 * 输出：[6,5,0,7,5]
 *
 * @author Jisheng Huang
 * @version 20250426
 */
public class QueryPermutationWithKey_1409 {
    /**
     * Simulation
     * 对于数组 queries 中的每一个询问项 query，我们在排列 P 中找到 query 所在的位置，并把它加入答案。随后，我们需要将 query
     * 移动到排列 P 的首部。具体地，我们首先将 query 从排列 P 中移除，再添加到排列 P 的首部即可。
     *
     * @param queries the given integer array
     * @param m       the length of the return array
     * @return an array with the given condition
     */
    public static int[] processQueries(int[] queries, int m) {
        List<Integer> p = new ArrayList<>();

        for (int i = 1; i <= m; ++i) {
            p.add(i);
        }

        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; ++i) {
            int query = queries[i];
            int pos = -1;

            for (int j = 0; j < m; ++j) {
                if (p.get(j) == query) {
                    pos = j;
                    break;
                }
            }

            ans[i] = pos;
            p.remove(pos);
            p.add(0, query);
        }

        return ans;
    }

    public static void main(String[] args) {
        int[] queries = {3, 1, 2, 1};
        int m = 5;
        int[] ans = processQueries(queries, m);

        for (int i : ans) {
            System.out.print(i + " ");
        }
        System.out.println();

        queries = new int[]{4, 1, 2, 2};
        m = 4;
        ans = processQueries(queries, m);

        for (int i : ans) {
            System.out.print(i + " ");
        }
        System.out.println();

        queries = new int[]{7, 5, 5, 8, 3};
        m = 8;
        ans = processQueries(queries, m);

        for (int i : ans) {
            System.out.print(i + " ");
        }
    }
}
